package com.leetcode;

/*
 For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
 the contiguous subarray [4,−1,2,1] has the largest sum = 6.
 */
public class MaxSubArray
{

	public static void main(String[] args)
	{
		MaxSubArray msa = new MaxSubArray();
		int[] a = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
		System.out.println(msa.maxSubArray(a));
	}

	public int maxSubArray(int[] A)
	{

		int sum = A[0];
		int cur = A[0];
		for (int i = 1; i < A.length; i++)
		{
			OutTxt.Write(cur+"--cur");
			if (cur < 0)
			{
				cur = A[i];
				OutTxt.Write(cur + "--cur<0");
			}
			else
			{
				cur += A[i];
				OutTxt.Write(cur + "--cur>=0");
			}
			if (sum < cur)
			{
				sum = cur;
				OutTxt.Write(sum + "--sum");
			}
		}
		return sum;
	}
}
